var rob = function (nums) {
    let memo = new Array(nums.length);
    memo.fill(-1, 0, nums.length)

    // 返回nums[start..]能抢到的最大值
    let dp = function (nums, start) {
        if (start >= nums.length) {
            return 0;
        }

        // 避免重复计算
        if (memo[start] !== -1) return memo[start];


        let res = Math.max(
            // 不抢，去下一家
            dp(nums, start + 1),

            // 抢， 然后去下下家抢
            nums[start] + dp(nums, start + 2)
        )

        // 记入备忘录
        memo[start] = res;

        return res;
    }

    // 强盗从第 0 间房子开始决定抢劫哪家
    return dp(nums, 0)
};


var rob = function (nums) {
    let n = nums.length;

    // dp[i] = x 表示：
    // 从第 i 间房子开始抢劫，最多能抢到的钱为 x
    // base case: dp[n] = 0
    let dp = new Array(n + 2);
    dp.fill(0, 0, n + 2)
    for (let i = n - 1; i >= 0; i--) {
        dp[i] = Math.max(
            dp[i + 1],
            nums[i] + dp[i + 2]
        )
    }
    // 强盗从第 0 间房子开始决定抢劫哪家
    return dp[0]
};

var rob = function (nums) {
    let n = nums.length;

    // 记录 dp[i+1] 和 dp[i+2]
    let dp_i_1 = 0, dp_i_2 = 0;

    // 记录 dp[i]
    let dp_i = 0;

    for (let i = n - 1; i >= 0; i--) {
        dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i;
};


var rob = function (nums) {
    let n = nums.length;

    if (n === 1) return nums[0];

    // 仅计算闭区间 [start,end] 的最优结果
    let robRange = function (nums, start, end) {
        let dp_i_1 = 0, dp_i_2 = 0;
        let dp_i = 0;
        for (let i = end; i >= start; i--) {
            dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }

    return Math.max(
        robRange(nums, 0, n - 2),
        robRange(nums, 1, n - 1)
    )
};


let memo = new Map();
var rob = function (root) {
    if (root === null) return 0;

    // 利用备忘录消除重叠子问题
    if (memo[root] !== undefined) {
        return memo.get(root);
    }

    // 抢，然后去下下家
    let do_it = root.val
        + (root.left === null ?
            0 : rob(root.left.left) + rob(root.left.right))
        + (root.right === null ?
            0 : rob(root.right.left) + rob(root.right.right));

    // 不抢，然后去下家
    let not_do = rob(root.left) + rob(root.right);


    let res = Math.max(do_it, not_do);
    memo.set(root, res);

    return res;
};


var rob = function (root) {
    let res = dp(root);

    return Math.max(res[0], res[1]);
};

var dp = function (root){
    if(root == null){
        return [0,0];
    }

    let left = dp(root.left);
    let right = dp(root.right);

    // 抢，下家就不能抢了
    let rob = root.val + left[0] + right[0];

    // 不抢，下家可抢可不抢，取决于收益大小
    let not_rob = Math.max(left[0], left[1]) + + Math.max(right[0], right[1]);

    return [not_rob, rob]
}

